package Demo3_2;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User：Lenovo
 * Date:2025-03-02
 * Time:22:25
 */
import java.util.PriorityQueue;

public class MinHeapExample {
    public static void main(String[] args) {
        // 创建一个最小堆
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        // 向最小堆中添加元素
        minHeap.add(5);
        minHeap.add(3);
        minHeap.add(7);
        minHeap.add(1);
        minHeap.add(9);

        // 打印最小堆中的元素
        System.out.println("最小堆中的元素: " + minHeap);

        // 移除并打印堆顶元素（最小值）
        while (!minHeap.isEmpty()) {
            int minElement = minHeap.poll();
            System.out.println("移除的最小元素: " + minElement);
        }
    }
}
//自定义是实现

//public class MinHeap {
//    private int[] heap;
//    private int size;
//    private int capacity;
//
//    public MinHeap(int capacity) {
//        this.capacity = capacity;
//        this.size = 0;
//        this.heap = new int[capacity];
//    }
//
//    private int parent(int i) {
//        return (i - 1) / 2;
//    }
//
//    private int leftChild(int i) {
//        return 2 * i + 1;
//    }
//
//    private int rightChild(int i) {
//        return 2 * i + 2;
//    }
//
//    private void swap(int i, int j) {
//        int temp = heap[i];
//        heap[i] = heap[j];
//        heap[j] = temp;
//    }
//
//    private void heapifyUp(int i) {
//        while (i > 0 && heap[parent(i)] > heap[i]) {
//            swap(parent(i), i);
//            i = parent(i);
//        }
//    }
//
//    private void heapifyDown(int i) {
//        int smallest = i;
//        int left = leftChild(i);
//        int right = rightChild(i);
//
//        if (left < size && heap[left] < heap[smallest]) {
//            smallest = left;
//        }
//
//        if (right < size && heap[right] < heap[smallest]) {
//            smallest = right;
//        }
//
//        if (smallest != i) {
//            swap(i, smallest);
//            heapifyDown(smallest);
//        }
//    }
//
//    public void insert(int key) {
//        if (size == capacity) {
//            System.out.println("堆已满，无法插入元素。");
//            return;
//        }
//
//        heap[size] = key;
//        size++;
//        heapifyUp(size - 1);
//    }
//
//    public int extractMin() {
//        if (size == 0) {
//            System.out.println("堆为空，无法提取元素。");
//            return -1;
//        }
//
//        int min = heap[0];
//        heap[0] = heap[size - 1];
//        size--;
//        heapifyDown(0);
//        return min;
//    }
//
//    public static void main(String[] args) {
//        MinHeap minHeap = new MinHeap(10);
//        minHeap.insert(5);
//        minHeap.insert(3);
//        minHeap.insert(7);
//        minHeap.insert(1);
//        minHeap.insert(9);
//
//        System.out.println("提取的最小元素: " + minHeap.extractMin());
//        System.out.println("提取的最小元素: " + minHeap.extractMin());
//    }
//}
